// ------------------------------------------------------------------------------------------------
// ---- Livro Algoritmos (de Dasgupta, Vazirani, Papadimitriou) -----------------------------------
// ---- Problema da DISTANCIA DE EDICÃO (Capítulo 6.2) --------------------------------------------
// ------------------------------------------------------------------------------------------------
#include <iostream>
#include <fstream>
#include <string>
#include <cmath>
#include <ctime>
#include <climits>
#include <windows.h>
using namespace std;


int EditDistance(string X, string Y, char**& op);

void imprime_edit_op(int i, int j, char** op, string X, string Y, string op1, string op2);
void imprime_matriz(string X, string Y, char** op);

// -------------------------------------------------------------
// --- MAIN ----------------------------------------------------
// -------------------------------------------------------------
int main() {
    unsigned int t1, t2;

    string X = "SNOWY";
    string Y = "SUNNY";
    int m = X.size();
    int n = Y.size();

    cout<<"Entrada X = "<<X<<endl;
    cout<<"Entrada Y = "<<Y<<endl<<endl;

    char** op = NULL;
    cout<<"Edit Distance = "<<EditDistance(X,Y,op)<<endl<<endl;

    string op1, op2;
    imprime_edit_op(m,n,op,X,Y,op1,op2);
    cout<<endl<<endl;

    imprime_matriz(X,Y,op);
    if (op!=NULL) {
        for (int i=0; i<=m; i++) delete[] op[i];
        delete[] op;
    }

    cout<<endl<<"Simbolo I (insert)"<<endl;
    cout<<"Simbolo D (delete)"<<endl;
    cout<<"Simbolo S (substituir)"<<endl<<endl;
    return 0;
}


// ------------------------------------------------------------------------------------------------
// ---- ALGORITMO EDIT-DISTANCE (distancia de edicao) ---------------------------------------------
// ------------------------------------------------------------------------------------------------
int EditDistance(string X, string Y, char**& op) {
    int i,j;    int m = X.size();
    int n = Y.size();
    int** E = new int*[m+1]; for (int i=0; i<=m; i++) E[i] = new int[n+1];
    if (op==NULL) {op=new char*[m+1]; for (int i=0; i<=m; i++) op[i] = new char[n+1];}

    for (i=0; i<=m; i++) E[i][0] = i;
    for (j=0; j<=n; j++) E[0][j] = j;

    for (i=1; i<=m; i++) {
        for (j=1; j<=n; j++) {
            if (X[i-1]==Y[j-1]) {
                E[i][j] = E[i-1][j-1];
                op[i][j] = ' ';
            } else if ((E[i-1][j]<=E[i][j-1])&&(E[i-1][j]<=E[i-1][j-1])) {
                E[i][j] = E[i-1][j] + 1;
                op[i][j] = 'I';
            } else if (E[i][j-1]<=E[i-1][j-1]) {
                E[i][j] = E[i][j-1] + 1;
                op[i][j] = 'D';
            } else {
                E[i][j] = E[i-1][j-1] + 1;
                op[i][j] = 'S';
            }
        }
    }
    int edit = E[m][n];
    for (i=0; i<=m; i++) delete[] E[i];
    delete[] E;
    return edit;
}



// -------------------------------------------------------------
// --- AUXILIARES ----------------------------------------------
// -------------------------------------------------------------
void imprime_edit_op(int i, int j, char** op, string X, string Y, string op1, string op2) {
    if ((i==0)&&(j==0)) {
        cout<<op1<<endl;
        cout<<op2<<endl<<endl;
        return;
    }
    if (op[i][j]=='I') {
        op1 = string(1,X[i-1]) + op1;
        op2 = "_" + op2;
        imprime_edit_op(i-1,j, op, X,Y,op1,op2);
        return;
    }
    if (op[i][j]=='D') {
        op1 = "_" + op1;
        op2 = string(1,Y[j-1]) + op2;
        imprime_edit_op(i,j-1, op, X,Y,op1,op2);
        return;
    }
    if ((op[i][j]=='S')||(op[i][j]==' ')) {
        op1 = string(1,X[i-1]) + op1;
        op2 = string(1,Y[j-1]) + op2;
        imprime_edit_op(i-1,j-1, op, X,Y,op1,op2);
        return;
    }
}

void imprime_matriz(string X, string Y, char** op) {
    int i,j;
    int m = X.size();
    int n = Y.size();

    cout<<"  "<<Y<<endl<<" ";
    for (j=0; j<=n; j++)  cout<<" ";
    cout<<endl;
    for (i=1; i<=m; i++) {
        cout<<X[i-1]<<" ";
        for (j=1; j<=n; j++) cout<<op[i][j];
        cout<<endl;
    }
}